#include <limits.h>  // INT_MIN,INT_MAX
#include <math.h>    // abs,pow

#include <algorithm>      // sort
#include <iostream>       // cout,cin
#include <numeric>        // accumulate
#include <string>         // string
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <vector>         // vector

using namespace std;

// 链表结点的数据结构
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

// 如果x是2的幂则返回True，否则返回False
bool IsPowerOf2(int x) { return (x & (x - 1)) == 0; }

class Solution {
   public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *node1 = head, *node2 = head;

        // 找到倒数第n+1个结点
        for (int i = 0; i < n + 1; i++) {
            if (node2 == nullptr) {  // 正在删除头结点的情况
                return head->next;
            }
            node2 = node2->next;
        }
        while (node2 != nullptr) {
            node1 = node1->next;
            node2 = node2->next;
        }

        node1->next = node1->next->next;
        return head;
    }
};

int main() {
    Solution solution;
    return 0;
}